package org.mte.sak.sort.impl;

import org.mte.sak.sort.AbstractSort;
import org.mte.sak.sort.comparator.Comparator;

/**
 * The quicksort algorithm.
 *
 * @author unknown
 * @version $Revision: 1.2 $ $Date: 2011-12-27 11:42:34 $
 *
 */
public class QuickSort extends AbstractSort {

    /**
     * sort
     */
    private static QuickSort sorter;

    /**
     * QuickSort
     */
    private QuickSort() {
    }

    /**
     * getInstance
     * @return instance
     */
    public static QuickSort getInstance() {
		if (sorter == null) {
		    sorter = new QuickSort();
		}
		return sorter;
    }

    /**
     * The quicksort function.
     *
     * @param keys the array with all keys.
     * @param objs the array with all objects.
     * @param start the start offset in the array.
     * @param end the end offset in the array.
     * @param comp The comparaison function between objects.
     */
    public void sort(Object[] keys, Object[] objs, int start, int end, Comparator comp) {
		if (start < end) {
			int median = partition(keys, objs, start, end, comp);
		    sort(keys, objs, start, median - 1, comp);
		    sort(keys, objs, median + 1, end, comp);
		}
	}

    /**
     * sort
     * @param keys
     * @param objs
     * @param comp
     * @see org.dromedary.lib.sort.Sortable#sort(java.lang.Object[], java.lang.Object[], org.dromedary.lib.sort.Comparator)
     */
	public void sort(Object[] keys, Object[] objs, Comparator comp) {
		sort(keys, objs, 0, keys.length - 1, comp);
	}

	/**
     * partition
     * @param keys
     * @param objs
     * @param indexPartLow
     * @param indexPartHigh
     * @param comp
     * @return int
	 */
    private int partition(Object[] keys, Object[] objs, int indexPartLow,
	   			int indexPartHigh, Comparator comp) {
		int lastSmall;
		int comp1;
		Object medianValue;

		// swap median value an first value of array
		comp1 = (indexPartLow + indexPartHigh ) / 2;
		swap(keys, indexPartLow, comp1);
		if (objs != null) {
			swap(objs, indexPartLow, comp1);
		}
		medianValue = keys[indexPartLow];

		lastSmall = indexPartLow;
		for (int i = indexPartLow + 1; i <= indexPartHigh; i++) {
		    if (comp.compare(keys[i], medianValue)) {
				lastSmall++;
				// swap lastSmall and i
				swap(keys, lastSmall, i);

				if (objs != null) {
					swap(objs, lastSmall, i);
				}
		    }
		}
		// swap indexPartLow and lastSmall
		swap(keys, indexPartLow, lastSmall);
		if (objs != null) {
			swap(objs, indexPartLow, lastSmall);
		}
		return lastSmall;
    }

    /**
     * swap
     * @param genericObjects
     * @param i
     * @param j
     */
    private void swap(Object[] genericObjects, int i, int j) {
		Object transitObj;
		transitObj = genericObjects[i];
		genericObjects[i] = genericObjects[j];
		genericObjects[j] = transitObj;
    }
}
